package bin_tree.leetcode;

/**
 * 另一棵树的子树
 */
public class Num572 {
    /**
     * 传入root和subroot
     * 判断subroot是否是root的子树
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 1.边界
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // r和s相同
        if (isSameTree(root,subRoot)) {
            return true;
        }
        // r.left是否包含s || r.right 是否包含s
        return isSubtree(root.left,subRoot)
                || isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 都是空树
        if (p == null && q == null) {
            return true;
        }
        // p和q有一个为空，另一个不为空
//        if (p != null && q == null) return false;
//        if (p == null && q != null) return false;
        if (p == null || q == null) {
            return false;
        }
        // p和q都不为空
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
